package com.lyt.springboot.util.algorithm;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;

public class S21 {
    //合并两个有序的数组
    public void merge(int A[], int m, int B[], int n) {
        for (int i = 0; i < n; i++) {
            A[m + i] = B[i];
        }
        Arrays.sort(A);
        //时间复杂度 mlogm+nlogn  =(m+n)log(m+n)  快排的时间复杂度
    }

    public void merge1(int A[], int m, int B[], int n) {
        System.arraycopy(B, 0, A, m, n);
    }


    public boolean judge(String str) {
        StringBuilder builder = new StringBuilder();
        StringBuilder reverse = builder.append(str).reverse();
        if (str.equals(reverse.toString())) {
            return true;

        } else {
            return false;
        }
    }


    public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
        Collections.sort(intervals, new Comparator<Interval>(){
            @Override
            public int compare(Interval o1, Interval o2){
                return o1.start - o2.start;
            }
        });
        ArrayList<Interval> arrList = new ArrayList<>();
        if(intervals == null || intervals.size() == 0) {
            return arrList;

        }
        //定义指针pre cur
        int pre = 0;
        int cur = 1;
        int size =  intervals.size();
        while(cur<size) {
            if(intervals.get(pre).end >= intervals.get(cur).start) {
                int end = Math.max(intervals.get(pre).end,intervals.get(cur).end);
                intervals.set(pre,new Interval(intervals.get(pre).start,end));
                intervals.remove(cur);
                size--;
            }else {
                pre++;
                cur++;
            }
        }
        return intervals;
    }
    public class Interval {
    int start;
    int end;
    public Interval(int start, int end) {
     this.start = start;
      this.end = end;
    }
  }
}
